package collection;

import java.util.Iterator;

public class MyLinkedList  implements Iterable<Integer>{
    private Node head;
    private Node tail;
    private int size;

    public void add(int value) {
        if (size == 0) { //没有数据
            head = new Node(value); //新建的第一个节点就是头部节点
            tail = head; //同时也是尾部节点
            size++;  //数据量+1
            return;
        }
        Node newNode = new Node(value);
        tail.next = newNode;  //尾部节点的下一个是新节点
        newNode.prev = tail;  //新节点的上一个是尾部节点
        tail = newNode;       //把尾部节点变量修改到newNode位置
        size++;               //数据量+1
    }

    /*
    - index<size/2，从head开始向后数数
    - 否则，从tail开始向前倒数
     */
    public int get(int index) {
        Node n = getNode(index);
        return n.value;
    }

    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界："+index);
        }
        if (index < size / 2) {  //前边一半数据中寻找
            Node n = head;       //临时变量，从第一个节点向后移动，直到index位置节点
            int count = 0;       //计数
            while (count < index) {  //还没有数到index位置，就继续往后
                n = n.next;          //n移到下一个位置
                count++;             //计数加1
            }
            return n;                //n引用的就是index位置的节点
        } else {                 //在后边一半寻找
            Node n = tail;       //n从尾部节点开始
            int count = size-1;  //计数从最后一个下标位置开始
            while (count > index) {     //还没有倒数到index位置，就继续向前
                n = n.prev;             //n向前移到前一个位置
                count--;                //计数减1
            }
            return n;                   //n引用的就是index位置的节点
        }
    }

    public int getFirst() {
        if (size == 0) {
            throw new RuntimeException("没有数据");
        }
        return head.value;
    }

    public int getLast() {
        if (size == 0) {
            throw new RuntimeException("没有数据");
        }
        return tail.value;
    }

    public int size() {
        return size;
    }

    public void remove(int index) {
        if (size == 0) {
            throw new IndexOutOfBoundsException("下标越界");
        }
        if (index == 0) {
            head = head.next;   //把头部节点的下一个，设置成新的头部节点
            head.prev = null;   //新的头部节点的前一个，设置成null
            size--;             //数据量减1
            return;
        } else if (index == size-1) {
            tail = tail.prev;
            tail.next = null;
            size--;
            return;
        }

        Node n = getNode(index);

        n.prev.next = n.next;  //n前一个节点的下一个，引用n的下一个节点
        n.next.prev = n.prev;  //n下一个节点的前一个，应用n的前一个节点

        size--;
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node n = head;

            @Override
            public boolean hasNext() {
                return n != null;
            }

            @Override
            public Integer next() {
                Node tmp = n;
                n = n.next;
                return tmp.value;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("不支持删除操作");
            }
        };
    }

    static class Node {
        private int value;
        private Node prev;
        private Node next;
        Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        System.out.println(list.size);
        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(5));
        System.out.println(list.get(7));
        System.out.println("--------------------------");
        list.remove(6);
        for (int i = 0; i < list.size; i++) {
            System.out.println(list.get(i));
        }
    }
}
